package personal.leil.learning.quick;

import personal.leil.learning.utils.ArrayUtils;

/**
 * 荷兰国旗问题
 * <p>
 * 给定一个数组和一个数，将数组小于、等于、大于该数的值分成三部分
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024-1-3
 */
public class FlagOfNetherlandsProblem {

    /**
     * 算法实现
     * <p>
     * 可以把数组分成3个区域，分别为小于、等于、大于目标数字的区域
     * </p>
     *
     * @param arr   source array
     * @param num   target number
     */
    public static void process(int[] arr, int num) {
        int l = 0,
                i = 0,
                r = arr.length - 1;
        while (i <= r) {
            if (arr[i] < num) {
                // 小于
                ArrayUtils.swap(arr, l++, i++);
            } else if (arr[i] > num) {
                // 大于
                ArrayUtils.swap(arr, r--, i);
            } else {
                // 等于
                i++;
            }
        }
    }


    /********************* For Test *************************/

    public static void main(String[] args) {
        int targetNum = 463;
        System.out.println("target num:" + targetNum);
        int[] arr = {861, 846, 615, 730, 982, 384, 437, 78, 28, 463, 774, 355, 971, 714, 123, 849, 374, 90, 741, 952};
        System.out.println("before process:");
        ArrayUtils.printArr(arr);
        process(arr, targetNum);
        System.out.println("after process:");
        ArrayUtils.printArr(arr);
    }


}
